package com.example.algorithm.service.impl;

import com.example.algorithm.service.GreedyService;
import org.springframework.stereotype.Service;

import java.util.ArrayList;
import java.util.List;

/**贪心算法
 * @author Administrator
 * @date 2024/8/7 16:22
 * @description
 */
@Service
public class GreedyServiceImpl implements GreedyService {
    /**NO.74 买卖股票的最佳时机
     * 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
     *
     * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
     *
     * 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
     * @param prices
     * @return
     * 解法一：暴力
     * 解法二：一次遍历
     * 解法三：动态规划
     * 解法四：单调栈
     *
     *
     */
    @Override
    public int maxProfit(int[] prices) {
        int maxtProfit =0;
        int left =0;
        int right=left+1;
        while (left<=right&&right<prices.length){
            maxtProfit = Math.max(maxtProfit,prices[right]-prices[left]);
            if(prices[left]>prices[right]){
                left++;
                continue;
            }
           right++;
        }
        return maxtProfit;
    }

    /**
     **NO.75 跳跃游戏
     * 给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
     *
     * 判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
     * @param nums
     * @return
     * 解法一：贪心算法
     * 解法二：逆向解
     *
     */
    @Override
    public boolean canJump(int[] nums) {
        int step=0;
        if(nums.length==1){
            return true;
        }
        for(int i=0;i<=step; i++){
            step=Math.max(step,nums[i]+i);
            if(step>= nums.length-1){
                return true;
            }


        }
        return false;
    }

    /**NO.76 跳跃游戏II
     * 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
     *
     * 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
     *
     * 0 <= j <= nums[i]
     * i + j < n
     * 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
     * @param nums
     * @return
     * 解法一：反向查找出发位置
     * 解法二：正向查找可到达的最大位置
     * 解法三：动态规划
     *
     */
    @Override
    public int jump(int[] nums) {
        int step=0;
        int currPos=0;
        int nextPos=0;
        for(int i=0;i<=nums.length-1; i++){
            if(i>currPos){
                currPos=nextPos;
                ++step;
            }
            nextPos = Math.max(nextPos,i+nums[i]);
        }
        return step;
    }

    /**NO.77 划分字母区间
     * 给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
     *
     * 注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
     *
     * 返回一个表示每个字符串片段的长度的列表。
     *
     *
     * @param s
     * @return
     * 解法一：贪心算法
     * 解法二：动态规划
     *
     *
     */
    @Override
    public List<Integer> partitionLabels(String s) {
        List<Integer> res = new ArrayList<>();
        int left =0;
        int right=s.lastIndexOf(s.charAt(0));
        for(int i=0;i<s.length();i++){
        right = Math.max(right,s.lastIndexOf(s.charAt(i)));
        if(i==right) {
            res.add(right - left + 1);
            left = right + 1;
        }
        }

        return res;
    }
}
